import java.util.*;

public class Text {

    //78
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> tmp = new LinkedList<>();

    public void func(int[] nums,int startIndex) {
        ret.add(new ArrayList<>(tmp));
        if(startIndex == nums.length) return;
        for(int i = startIndex; i < nums.length; i++) {
            tmp.add(nums[i]);
            func(nums,i+1);
            tmp.remove(tmp.size()-1);
        }
    }

    //90
    public List<List<Integer>> subsets(int[] nums) {
        func(nums,0);
        return ret;
    }
    public void func(int[] nums,int startIndex,int[] used) {
        ret.add(new ArrayList<>(tmp));
        if(startIndex >= nums.length) return;
        for(int i = startIndex; i < nums.length; i++) {
            if(i >= 1 && nums[i] == nums[i-1] && used[i-1] == 0) {
                continue;
            }else {
                used[i] = 1;
                tmp.add(nums[i]);
            }
            func(nums,i+1,used);
            used[i] = 0;
            tmp.remove(tmp.size()-1);
        }
    }
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        int[] used = new int[nums.length];
        func(nums,0,used);
        return ret;
    }
}
